﻿#define _CRT_SECURE_NO_WARNINGS 1
//题目：图中点的层次（树与图的宽度优先遍历）
//给定一个 n个点 m条边的有向图，图中可能存在重边和自环。
//所有边的长度都是 1，点的编号为 1∼n。
//请你求出 1号点到 n号点的最短距离，如果从 号点无法走到 n号点，输出 −1。
//输入格式
//第一行包含两个整数 n和 m。
//接下来 m行，每行包含两个整数 a和 b，表示存在一条从 a走到 b的长度为 1的边。
//输出格式
//输出一个整数，表示 1号点到 n号点的最短距离。
//数据范围
//1≤n, m≤105
//输入样例：
//4 5
//1 2
//2 3
//3 4
//1 3
//1 4
//输出样例：
//1
//#include<iostream>
//#include<cstring>
//#include<algorithm>
//using namespace std;
//const int N = 100010;
//int h[N], e[N], ne[N], idx;
//int q[N],//存储节点
//d[N];//存储距离
//int n, m;
//void add(int a, int b)
//{
//    e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
//}
//int bfs()
//{
//    int hh = 0, tt = 0;
//    q[0] = 1;
//    memset(d, -1, sizeof d);
//    d[1] = 0;
//    while (hh <= tt)
//    {
//        int t = q[hh++];
//        for (int i = h[t]; i != -1; i = ne[i])
//        {
//            int j = e[i];
//            if (d[j] == -1)//如果距离没有走过从进入，如果不等于-1就代表的最短距离
//            {
//                d[j] = d[t] + 1;
//                q[++tt] = j;
//            }
//        }
//    }
//    return d[n];
//}
//int main()
//{
//    cin >> n >> m;
//    memset(h, -1, sizeof(h));
//
//    for (int i = 0; i < m; i++)
//    {
//        int a, b;
//        cin >> a >> b;
//        add(a, b);
//    }
//    cout << bfs() << endl;
//    return 0;
//}

//题目：有向图的拓扑排序
//给定一个 n个点 m条边的有向图，点的编号是 1到 n，图中可能存在重边和自环。
//请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。
//若一个由图中所有点构成的序列 A满足：对于图中的每条边(x, y)，x在 A中都出现在 y之前，则称 A是该图的一个拓扑序列。
//输入格式
//第一行包含两个整数 n和 m。
//接下来 m行，每行包含两个整数 x和 y，表示存在一条从点 x到点 y的有向边(x, y)。
//输出格式
//共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。
//否则输出 −1。
//数据范围
//1≤n, m≤105
//输入样例：
//3 3
//1 2
//2 3
//1 3
//输出样例：
//1 2 3
//#include<iostream>
//#include<algorithm>
//#include<cstring>
////一个有向无环图，一定至少存在一个入度为0 的点
//using namespace std;
//const int N = 100010;
//int h[N], e[N], ne[N], idx;
//int q[N],
//d[N];//存储度的个数，度为0 的点先入队
//int n, m;
//void add(int a, int b)
//{
//    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
//}
//bool TopSort()
//{
//    int hh = 0, tt = -1;
//    for (int i = 1; i <= n; i++)
//    {
//        if (!d[i])
//            q[++tt] = i;
//    }
//    while (hh <= tt)
//    {
//        int t = q[hh++];
//        for (int i = h[t]; i != -1; i = ne[i])
//        {
//            int j = e[i];
//            if (--d[j] == 0)//如果度为0就可以入队，因为度不为0的话，还有别的点指向该节点，导致重复入队
//            {
//                q[++tt] = j;
//            }
//        }
//    }
//    return tt == n - 1;//如果节点全部入队了，就是拓扑排序了，将队列按顺序输出
//}
//int main()
//{
//    cin >> n >> m;
//    memset(h, -1, sizeof h);
//    for (int i = 0; i < m; i++)
//    {
//        int a, b;
//        cin >> a >> b;
//        add(a, b);
//        d[b]++;
//    }
//    if (TopSort())
//    {
//        for (int i = 0; i < n; i++)
//            printf("%d ", q[i]);
//    }
//    else puts("-1");
//    return 0;
//}